package Interview.Gas;

import javax.xml.crypto.dsig.keyinfo.RetrievalMethod;

public class Gas {
    
}


// 134. 加油站
class Solution_five {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        final int len = gas.length;
        for(int i=0;i<len;i++){
            int v = gas[i] - cost[i];
            int cur = (i+1)%len;
            while(v>=0){
                if(cur==i) return i;
                v+=gas[cur];
                v-=cost[cur];
                cur=(cur+1)%len;
            }
        }
        return -1;
    }
}


class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        final int len = gas.length;
        int total = 0;
        int has = 0;
        int start = 0;
        for(int i=0;i<len;i++){
            total+= gas[i]-cost[i];   //只要总的油量>消耗的肯定可以跑完
            has+= gas[i]-cost[i];    //记录从开始点开始剩下的油量，
                                    //如果<0的话表示从开始点到现在这个点之间所有点都没办法作为开始点
                                    //
            if(has<0){
                start = i+1;
                has = 0;
            }
        } 
        return total>=0?start:-1;  
    }
}